import java.util.*;

/**
 * @Author: YCKOKO
 * @Date: 2023-04-07
 * @Time:21:13
 * @Description:
 */
public class Graph4 {
    private static int INF = Integer.MAX_VALUE;
    private int[][] Edges;
    private int numOfedge;


    public Graph4(int n) {
        Edges = new int[n][n];
        numOfedge = 0;
    }


    public void addDirectedEdge(int src,int dest,int weight){
        Edges[src][dest] = weight;
        numOfedge++;
    }

    public void addUndirectedEdge(int src,int dest,int weight){
        addDirectedEdge(src,dest,weight);
        addDirectedEdge(dest,src,weight);
    }

    public List<Integer> getNighbors(int start){
        List<Integer> Nighbors = new ArrayList<>();
        for (int i = 0; i < Edges[start].length; i++) {
            if(Edges[start][i] > 0){
                Nighbors.add(i);
            }
        }
        return Nighbors;
    }

    public boolean hasEdge(int src,int dest){
        return Edges[src][dest] > 0 || Edges[dest][src] > 0;
    }

    public int getWeight(int src,int dest){
        return Edges[src][dest];
    }

    public void showGraph(){
        for (int[] edges: Edges) {
            System.out.println(Arrays.toString(edges));
        }
    }

    public void dfs(int vertex){
        HashSet<Integer> visited = new HashSet<>();
        dfsHelper(vertex,visited);
        System.out.println();
    }

    public void dfsHelper(int vertex,HashSet<Integer> visited){
        System.out.print(vertex + " ");
        visited.add(vertex);
        for (int i = 0; i < Edges[vertex].length; i++) {
            if(Edges[vertex][i]>0 && !visited.contains(i)){
                dfsHelper(i,visited);
            }
        }
    }

    public void bfs(int vertex){
        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(vertex);
        visited.add(vertex);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            System.out.print(cur + " ");
            for (int i = 0; i < Edges[cur].length; i++) {
                if(Edges[cur][i] > 0 && !visited.contains(i)){
                    queue.offer(i);
                    visited.add(i);
                }
            }
        }
    }

    public int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        Arrays.fill(dist,INF);

        for (int i = 0; i < n; i++) {
            dist[i] = graph[start][i];
        }

        visited[start] = true;

        for (int i = 0; i < n; i++) {
            int min_dist = INF;
            int middle = 0;

            for (int j = 0; j < n; j++) {
                if(!visited[j] && min_dist > dist[j]){
                    min_dist = dist[j];
                    middle = j;
                }
            }
            visited[middle] = true;
            for (int j = 0; j < n; j++) {
                if(!visited[j]&&dist[j]>dist[middle]+graph[middle][j]){
                    dist[j]=dist[middle]+graph[middle][j];
                }
            }
        }
        return dist;
    }


    public static void main(String[] args) {
        Graph4 graph = new Graph4(4);

        //添加边Edge
        graph.addDirectedEdge(0, 1, 10);
        graph.addDirectedEdge(0, 2, 20);
        graph.addDirectedEdge(1, 2, 5);
        graph.addDirectedEdge(2, 3, 15);
        graph.addDirectedEdge(1, 3, 20);

        graph.showGraph();

//        System.out.println(graph.hasEdge(1, 4));
//        System.out.println(graph.hasEdge(1, 3));
//
//        System.out.println(graph.getWeight(1, 2));
//
//        System.out.println(graph.numOfedge);
//        System.out.println(graph.getNighbors(1));

//        graph.dfs(2);
//        graph.bfs(1);
        int[] dists = graph.dijkstra(graph.Edges, 0);
        for (int dist: dists) {
            System.out.println(dist);
        }

    }


}
